package com;

/**
 * @author liujunjie
 * @create 2021-12-13 16:09
 */
public class KnapsackProblem {

    /**
     * 动态规划算法
     * 应用实例：0-1背包问题（限制每个物品要么拿（1个），要么不拿（0个））
     */
        public static void main(String[] args) {
            // 每个物品的重量
            int[] weight = {1, 2, 4};
            // 每个物品的价值
            int[] value = {40, 30, 10};
            // 背包的容量
            int m = 4;
            // 物品的个数
            int n = value.length;

            // v[i][j] 表示在前i个物品中进行组合后装入容量为j的背包中的最大价值
            int[][] v = new int[n+1][m+1];
            // 记录放入物品的情况
            int[][] path = new int[n+1][m+1];

            // 二维数组 int[][] v 的第一行与第一列的初始化
            // 可以不处理，默认就是0
            for(int i = 0; i < v[0].length; i++) {
                v[0][i] = 0;
            }
            for(int i = 0; i < v.length; i++) {
                v[i][0] = 0;
            }

            // 实现 0-1背包 中物品的最大值
            // i 可理解为：第i个物品（行代表具有重量与价值的不用物品）
            // j 可理解为：背包的不同容量（列代表不同容量的背包）
            // v[i][j] 表示在前i个物品中进行组合后装入容量为j的背包中的最大价值
            for(int i = 1; i < v.length; i++) {  // 循环取出每一个物品
                for(int j = 1; j < v[0].length; j++) { // 前i个物品在不用容量j的背包下的最大价值
                    // weight[i-1] value[i-1] 解释：i的初始值为1（i= 1），代表第一个物品，但是在weight[]中
                    // 第一个物品的下标索引为0，索引要 i - 1 指向第一个物品
                    if(weight[i-1] > j) { // 第i个物品的重量大于当前背包的容量j
                        v[i][j] = v[i-1][j];
                    } else {
                        if(v[i-1][j] < value[i-1] + v[i-1][j-weight[i-1]]) {
                            v[i][j] = value[i-1] + v[i-1][j-weight[i-1]];
                            // 记录第i个物品放入背包的情况
                            path[i][j] = 1;
                        } else {
                            v[i][j] = v[i-1][j];
                        }
                    }
                }
            }

            // 不用容量的背包中物品的最大价值
            for(int i =0; i < v.length; i++) {
                for(int j = 0; j < v[i].length; j++) {
                    System.out.print(v[i][j] + "\t");
                }
                System.out.println();
            }
		/*0	0	0	0	0
		0	40	40	40	40
		0	40	40	70	70
		0	40	40	70	70*/

            System.out.println("============================");

            for(int i = 0; i < path.length; i++) {
                for(int j = 0; j < path[i].length; j++) {
                    if(path[i][j] == 1) {
                        System.out.println("第 " + i + " 个物品放入了背包");
                    }
                }
            }
		/*第 1 个物品放入了背包
		第 1 个物品放入了背包
		第 1 个物品放入了背包
		第 1 个物品放入了背包
		第 2 个物品放入了背包
		第 2 个物品放入了背包*/

            System.out.println("============================");

            // i j 初始化指向二维数组v[][]的最后一个单元格，即为0-1背包问题的最优解（背包中物品的最大价值）
            // 循环判断第i个物品是否放入了容量为j的背包中（path[i][j] == 1），
            // 如果放入了，则求出背包的剩余容量（j -= weight[i-1]），继续判断第i-1（i--）个物品是否放入容量为j的背包中
            // 如果没放入，则判断前一个物品（i--）是否放入了容量为j的背包中
            // weight[i-1] 解释：i的初始值为i = path.length - 1（i=3），代表最后一个物品，但是在weight[]中
            // 最后一个物品的下标索引为2，索引要 i - 1 指向最后一个物品
            int i = path.length - 1;
            int j = path[0].length - 1;
            while(i > 0 && j > 0 ) {
                if(path[i][j] == 1) {
                    System.out.println("第 " + i + " 个物品放入了背包，" + "其重量为 " + weight[i-1] + "，价值为 " + value[i-1]);
                    j -= weight[i-1];
                }
                i--;
            }
		/*第 2 个物品放入了背包，其重量为 2，价值为 30
		第 1 个物品放入了背包，其重量为 1，价值为 40*/
        }
    }
